/* AI.java
 * This class is responsible for making moves for the computer player in the 4-d tic-tac-toe game
 * The class is designed to make moves of various skill levels, given a board.
 * 
 */

package tictactoe;

import java.util.ArrayList;
import java.util.Random;

public class AI {
	/* Constructor: The class stores no information, so its only instance variable is a random number generator */
	public AI() {
		rand = new Random();
	}

	/* input: a 4-dimensional array of Marker objects board
	 *        a boolean x_turn, which is true if and only if it is x's turn to move
	 *        an integer difficulty that is 0 for an easy move, 1 for a medium
	 *        difficulty move, or 2 for a hard move
	 */
	public int[] move(Marker[][][][] board, boolean x_turn, int difficulty) {
		if (difficulty == 0) {
			return moveEasy(board, x_turn);
		}
		if (difficulty == 1) {
			return moveMedium(board, x_turn);
		}
		if (difficulty == 2) {
			return moveHard(board, x_turn);
		}
		return null;
	}
	
	// This is an enumerated type used to classify moves by their outcome
	enum MoveType{Win,Block,Fork,BlockFork,Threaten,BlockThreat,MakePair,Impossible,Other};
	
	//Returns an easy move given a board and player to move
	private int[] moveEasy(Marker[][][][] board, boolean x_turn) {
		/* The prob_[option] variables represent the probability that given
		 * the presence of a move option of a given type, it will take it.
		 * For example, if there are 3 winning moves, it will select one with
		 * probability .7.
		 */
		double prob_win = .7;
		double prob_block = .7;
		double prob_fork = .3;
		double prob_block_fork = .5;
		double prob_threaten = .7;
		double prob_block_threat = .5;
		double prob_make_pair = .9;
		// returns the move type associated with each square
		MoveType[][][][] optiontypes = get_move_type(board,x_turn);
		
		/* moves down list, choosing move of type "type" with probability prob_type 
		 * if a move is not chosen from one type, falls through to other options
		 */
		int[] answer = this.maybePickMove(optiontypes, MoveType.Win, prob_win);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.Block, prob_block);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.Fork, prob_fork);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.BlockFork, prob_block_fork);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.Threaten, prob_threaten);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.BlockThreat, prob_block_threat);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.MakePair, prob_make_pair);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.Other, 1);
		/* There is a chance that every move type that was not "Other"
		 * was skipped and there are no moves in the other category. If this is
		 * the case, go back through the array and choose the first available
		 * move. If the board is full, and there are no moves to be made, null
		 * will be returned. 
		 */
		if(answer!= null){
			return answer;
		};
		return chooseFirstOpen(board);
	}

	//Returns a medium move given a board and player to move
	private int[] moveMedium(Marker[][][][] board, boolean x_turn) {
		/* functions the same as moveEasy with different probabilities, see above */
		double prob_win = .8;
		double prob_block = .9;
		double prob_fork = .4;
		double prob_block_fork = .7;
		double prob_threaten = .5;
		double prob_block_threat = .9;
		double prob_make_pair = .9;
		MoveType[][][][] optiontypes = get_move_type(board,x_turn);
		

		int[] answer = this.maybePickMove(optiontypes, MoveType.Win, prob_win);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.Block, prob_block);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.Fork, prob_fork);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.BlockFork, prob_block_fork);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.Threaten, prob_threaten);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.BlockThreat, prob_block_threat);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.MakePair, prob_make_pair);
		if(answer!= null){
			return answer;
		}
		answer = this.maybePickMove(optiontypes, MoveType.Other, 1);
		if(answer!= null){
			return answer;
		};
		return chooseFirstOpen(board);

	}

	//Returns a hard move given a board and player to move
	private int[] moveHard(Marker[][][][] board, boolean x_turn) {
		int board_length = board.length;
		/* weights is the value assigned to each square. Squares are given weights
		 * by assigning values to different rows. The value of the square is the sum
		 * of the values of the rows through it.
		 * See getWeight method.
		 */
		//each weight is initialized to 0
		int[][][][] weights = new int[board_length][board_length][board_length][board_length];
		for (int i = 0; i < board_length; i++) {
			for (int j = 0; j < board_length; j++) {
				for (int k = 0; k < board_length; k++) {
					for (int l = 0; l < board_length; l++) {
						weights[i][j][k][l] = 0;
					}
				}
			}
		}
		/* For every row, count the number of x's and the number of o's in the row.
		 * Call getWeight to determine value of the row.
		 * Add the value of the row to each of its squares.
		 */
		Row row = new Row();
		do {
			int x_count = 0;
			int o_count = 0;
			for (int itr = 0; itr < board_length; itr++) {
				Square s = row.getSquare(itr, board_length);
				Marker marker = board[s.coord1][s.coord2][s.coord3][s.coord4];
				if (marker == Marker.X) {
					x_count++;
				}
				if (marker == Marker.O) {
					o_count++;
				}
			}
			int weight = getWeight(x_count, o_count, x_turn);
			for (int itr = 0; itr < board_length; itr++) {
				Square s = row.getSquare(itr, board_length);
				weights[s.coord1][s.coord2][s.coord3][s.coord4] += weight;
			}
		} while (row.next(board_length));
		/* Loop through all the squares, to find the one with the largest value.
		 * Return the coordinates of that square
		 */
		
		int max_weight = -10;
		int[] answer = new int[board_length];
		for (int dim1 = 0; dim1 < board_length; dim1++) {
			for (int dim2 = 0; dim2 < board_length; dim2++) {
				for (int dim3 = 0; dim3 < board_length; dim3++) {
					for (int dim4 = 0; dim4 < board_length; dim4++) {
						/* replace if a better move is found.
						 * If an equal strength move is found, replace with probability
						 * .5. This prevents the AI from playing the same moves all
						 * the time.
						 */
						if ((weights[dim1][dim2][dim3][dim4] > max_weight
								    && board[dim1][dim2][dim3][dim4] == Marker.Empty)
								|| (weights[dim1][dim2][dim3][dim4] == max_weight 
								    && rand.nextDouble() < .5)) {
							max_weight = weights[dim1][dim2][dim3][dim4];
							answer[0] = dim1;
							answer[1] = dim2;
							answer[2] = dim3;
							answer[3] = dim4;
						}
					}
				}
			}
		}

		return answer;

	}

	/* Input: 4x4x4x4 Marker array, board that specifies the current state of
	 * a tic-tac-toe-game
	 *        a boolean, x_turn, which is true if and only if it is x's turn to move.
	 * Output: 4x4x4x4 dimensional MoveType array that specifies what class of move each
	 * square on the board falls into
	 * Note: classification depends on board being of length 4
	 */
	private MoveType[][][][] get_move_type(Marker[][][][] board, boolean x_turn) {

		// The number of rows through each square with 3 of player's markers
		boolean[][][][] triples = new boolean[4][4][4][4];
		// The number of rows through each square with 3 of opponent's markers
		boolean[][][][] enemytriples = new boolean[4][4][4][4];
		// The number of rows through each square with 2 of player's markers
		int[][][][] pairs = new int[4][4][4][4];
		// The number of rows through each square with 2 of opponent's markers
		int[][][][] enemypairs = new int[4][4][4][4];
		// The number of rows through each square with 1 of player's markers
		boolean[][][][] singles = new boolean[4][4][4][4];
		// initialize all arrays to 0
		for(int dim1 = 0; dim1 < 4; dim1++) {
			for(int dim2 = 0; dim2 < 4; dim2++) {
				for(int dim3 = 0; dim3 < 4; dim3++) {
					for(int dim4 = 0; dim4 < 4; dim4++) {
						triples[dim1][dim2][dim3][dim4] = false;
						enemytriples[dim1][dim2][dim3][dim4] = false;
						pairs[dim1][dim2][dim3][dim4] = 0;
						enemypairs[dim1][dim2][dim3][dim4] = 0;
					}
				}
			}
		}
		/* For each row, count x's and o's. Increment array that keeps track of the
		 * type of row (triple, double, enemy triple, etc) at all square locations in
		 * the row.
		 */
		Row row = new Row();
		do {
			int x_count = 0;
			int o_count = 0;
			for (int itr = 0; itr < 4; itr++) {
				Square s = row.getSquare(itr, 4);
				Marker marker = board[s.coord1][s.coord2][s.coord3][s.coord4];
				if (marker == Marker.X) {
					x_count++;
				}
				if (marker == Marker.O) {
					o_count++;
				}
			}
			if(x_count > 0 && o_count > 0) {
				continue;
			}
			for (int itr = 0; itr < 4; itr++) {
				Square s = row.getSquare(itr, 4);
				if(x_turn) {
					if(x_count == 3) {
						triples[s.coord1][s.coord2][s.coord3][s.coord4] = true;
					}
					if(x_count == 2) {
						pairs[s.coord1][s.coord2][s.coord3][s.coord4]++;
					}
					if(x_count == 1) {
						singles[s.coord1][s.coord2][s.coord3][s.coord4] = true;
					}
					if(o_count == 3) {
						enemytriples[s.coord1][s.coord2][s.coord3][s.coord4] = true;
					}
					if(o_count == 2) {
						enemypairs[s.coord1][s.coord2][s.coord3][s.coord4]++;
					}
				}
				else {
					if(o_count == 3) {
						triples[s.coord1][s.coord2][s.coord3][s.coord4] = true;
					}
					if(o_count == 2) {
						pairs[s.coord1][s.coord2][s.coord3][s.coord4]++;
					}
					if(o_count == 1) {
						singles[s.coord1][s.coord2][s.coord3][s.coord4] = true;
					}
					if(x_count == 3) {
						enemytriples[s.coord1][s.coord2][s.coord3][s.coord4] = true;
					}
					if(x_count == 2) {
						enemypairs[s.coord1][s.coord2][s.coord3][s.coord4]++;
					}
				
				}
			}
		} while (row.next(4));

		/* For each square, classify move type according to number of diagonals
		 * of different types through the row.
		 */
		MoveType[][][][] result = new MoveType[4][4][4][4];
		for(int dim1 = 0; dim1 < 4; dim1++) {
			for(int dim2 = 0; dim2 < 4; dim2++) {
				for(int dim3 = 0; dim3 < 4; dim3++) {
					for(int dim4 = 0; dim4 < 4; dim4++) {
						if(board[dim1][dim2][dim3][dim4] != Marker.Empty) {
							result[dim1][dim2][dim3][dim4] = MoveType.Impossible;
						} else if(triples[dim1][dim2][dim3][dim4]) {
							result[dim1][dim2][dim3][dim4] = MoveType.Win;
						} else if(enemytriples[dim1][dim2][dim3][dim4]) {
							result[dim1][dim2][dim3][dim4] = MoveType.Block;
						} else if(pairs[dim1][dim2][dim3][dim4] >= 2) {
							result[dim1][dim2][dim3][dim4] = MoveType.Fork;
						} else if(enemypairs[dim1][dim2][dim3][dim4] >= 2) {
							result[dim1][dim2][dim3][dim4] = MoveType.BlockFork;
						} else if(pairs[dim1][dim2][dim3][dim4] == 1) {
							result[dim1][dim2][dim3][dim4] = MoveType.Threaten;
						} else if(enemypairs[dim1][dim2][dim3][dim4] >= 1) {
							result[dim1][dim2][dim3][dim4] = MoveType.BlockThreat;
						} else if(singles[dim1][dim2][dim3][dim4]) {
							result[dim1][dim2][dim3][dim4] = MoveType.MakePair;
						} else {
							result[dim1][dim2][dim3][dim4] = MoveType.Other;
						}
					}
				}
			}
		}
		return result;
	}
	
	/* Input: 4x4x4x4 MoveType array optiontypes
	 * MoveType option_chosen, the move type to look for
	 * prob_pick_move, a double that specifies the probability of choosing a random
	 * move of the given type.
	 * Output: if a move of the given type was selected, an array containing the
	 * coordinates of the move.
	 * if a move of the given type was not selected, returns null 
	 */
	private int[] maybePickMove(MoveType[][][][] optiontypes, MoveType option_chosen, double prob_pick_move) {
		int board_length = 4;
		ArrayList<Square> options = new ArrayList<Square>();
		//Add all squares of the specified move type to option.
		for (int dim1 = 0; dim1 < board_length; dim1++) {
			for (int dim2 = 0; dim2 < board_length; dim2++) {
				for (int dim3 = 0; dim3 < board_length; dim3++) {
					for (int dim4 = 0; dim4 < board_length; dim4++) {
						if(optiontypes[dim1][dim2][dim3][dim4] == option_chosen) {
							options.add(new Square(dim1,dim2,dim3,dim4));
						}
					}
				}
			}
		}
		/* If there are options, with probability pick_move, choose a random move
		 * from the list.
		 */
		if(options.size() != 0 && rand.nextDouble() < prob_pick_move) {
			int index = rand.nextInt(options.size());
			int[] move = new int[board_length];
			move[0] = options.get(index).coord1;
			move[1] = options.get(index).coord2;
			move[2] = options.get(index).coord3;
			move[3] = options.get(index).coord4;
			return move;
		}
		// If no move chosen, return null
		return null;
	}
	

	/* Input: a 4x4x4x4 Marker array, board
	 * Output: an array, containing the coordinates of the first empty square.
	 * If there are no empty squares, the return type is null.
	 */
	private int[] chooseFirstOpen(Marker[][][][] board) {
		int board_length = 4;
		for (int dim1 = 0; dim1 < board_length; dim1++) {
			for (int dim2 = 0; dim2 < board_length; dim2++) {
				for (int dim3 = 0; dim3 < board_length; dim3++) {
					for (int dim4 = 0; dim4 < board_length; dim4++) {
						if(board[dim1][dim2][dim3][dim4] == Marker.Empty) {
							int[] result = new int[4];
							result[0] = dim1;
							result[1] = dim1;
							result[2] = dim1;
							result[3] = dim1;
							return result;
						}
					}
				}
			}
		}
		return null;
	}
	
	/* This method is intended to take the number of x's and o's in a row
	 * along with the player from whose perspective the row is to be evaluated
	 * This weight is used to determine the value of a square. The value of a square
	 * is the sum of the weights of values of rows that go through it.
	 */
	private int getWeight(int x_count, int o_count, boolean x_turn) {

		/*If both players have a marker in the row, neither can win
		 * and the row is of no use to anyone
		 */
		if (x_count > 0 && o_count > 0)
			return 0;
		/* Add a bonus to rows of the current player's color. This causes the AI
		 * to be more aggressive, to win instead of block, and to fork
		 * instead of blocking a fork
		 * if x_count is positive then own_streak_bonus is equal to x_turn
		 * if o_count is positive, then own_streak_bonus is equal to the inverse
		 * of x_turn
		 * If the row is empty, then there is no bonus
		 */
		boolean own_streak_bonus = x_turn;
		int count = x_count; // count is the number of markers in the square
		                     //all markers should be the same color
		if (count == 0) {
			count = o_count;
			own_streak_bonus = !own_streak_bonus;
		}
		/* The weights for the different number of squares in a row were chosen
		 * by test. However, there are a few details that should be preserved if
		 * adjustments are to be made.
		 * 	* Win and block should be the most valuable options, so a count of 3 should
		 *    be weighted most heavily
		 *  * A squares with 2 rows of weight 2 represents a forking option, so it
		 *    should be second most valuable
		 */
		
		int result = 0;
		if (count == 3)
			result = 5000;
		else if (count == 2)
			result = 2000;
		else if (count == 1)
			result = 500;
		else
			result = 5;
		if (own_streak_bonus && count != 0)
			result += 10;
		return result;

	}
	
	Random rand;

}